//<p>给你一个下标从 <strong>1</strong> 开始、长度为 <code>n</code> 的整数数组 <code>nums</code> 。</p>
//
//<p>现定义函数 <code>greaterCount</code> ，使得 <code>greaterCount(arr, val)</code> 返回数组 <code>arr</code> 中<strong> 严格大于</strong> <code>val</code> 的元素数量。</p>
//
//<p>你需要使用 <code>n</code> 次操作，将 <code>nums</code> 的所有元素分配到两个数组 <code>arr1</code> 和 <code>arr2</code> 中。在第一次操作中，将 <code>nums[1]</code> 追加到 <code>arr1</code> 。在第二次操作中，将 <code>nums[2]</code> 追加到 <code>arr2</code> 。之后，在第 <code>i</code> 次操作中：</p>
//
//<ul> 
// <li>如果 <code>greaterCount(arr1, nums[i]) &gt; greaterCount(arr2, nums[i])</code> ，将 <code>nums[i]</code> 追加到 <code>arr1</code> 。</li> 
// <li>如果 <code>greaterCount(arr1, nums[i]) &lt; greaterCount(arr2, nums[i])</code> ，将 <code>nums[i]</code> 追加到 <code>arr2</code> 。</li> 
// <li>如果 <code>greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i])</code> ，将 <code>nums[i]</code> 追加到元素数量较少的数组中。</li> 
// <li>如果仍然相等，那么将 <code>nums[i]</code> 追加到 <code>arr1</code> 。</li> 
//</ul>
//
//<p>连接数组 <code>arr1</code> 和 <code>arr2</code> 形成数组 <code>result</code> 。例如，如果 <code>arr1 == [1,2,3]</code> 且 <code>arr2 == [4,5,6]</code> ，那么 <code>result = [1,2,3,4,5,6]</code> 。</p>
//
//<p>返回整数数组 <code>result</code> 。</p>
//
//<p>&nbsp;</p>
//
//<p><strong class="example">示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [2,1,3,3]
//<strong>输出：</strong>[2,3,1,3]
//<strong>解释：</strong>在前两次操作后，arr1 = [2] ，arr2 = [1] 。
//在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
//在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
//在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
//因此，连接形成的数组 result 是 [2,3,1,3] 。
//</pre>
//
//<p><strong class="example">示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [5,14,3,1,2]
//<strong>输出：</strong>[5,3,1,2,14]
//<strong>解释：</strong>在前两次操作后，arr1 = [5] ，arr2 = [14] 。
//在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
//在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 &gt; 1），因此，将 nums[4] 追加到 arr1 。
//在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 &gt; 1），因此，将 nums[5] 追加到 arr1 。
//在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
//因此，连接形成的数组 result 是 [5,3,1,2,14] 。
//</pre>
//
//<p><strong class="example">示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [3,3,3,3]
//<strong>输出：</strong>[3,3,3,3]
//<strong>解释：</strong>在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
//因此，连接形成的数组 result 是 [3,3,3,3] 。
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul> 
// <li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li> 
// <li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li> 
//</ul>
//
//<div><li>👍 21</li><li>👎 0</li></div>

#include <bits/stdc++.h>

#include "help_struct.h"
using namespace std;


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    struct Node {
        int v;
        Node *left, *right;

        Node()
            : v(0), left(nullptr), right(nullptr) {
        }
    };

    void push_down(Node* o, int l, int r) {
        if (o->left == nullptr) o->left = new Node();
        if (o->right == nullptr) o->right = new Node();
    }

    void push_up(Node* o) {
        o->v = o->left->v + o->right->v;
    }

    void update(Node* o, int l, int r, int p, int add) {
        if (r < p || l > p) return;
        if (l == r) {
            o->v += add;
            return;
        }
        int m = l + (r - l) / 2;
        push_down(o, l, r);
        if (p <= m) {
            update(o->left, l, m, p, add);
        } else {
            update(o->right, m + 1, r, p, add);
        }
        push_up(o);
    };

    int query(Node* o, int l, int r, int qL, int qR) {
        if (qL <= l && r <= qR) {
            return o->v;
        }
        int m = l + (r - l) / 2;
        int res = 0;
        push_down(o, l, r);
        if (qL <= m) {
            res += query(o->left, l, m, qL, qR);
        }
        if (qR > m) {
            res += query(o->right, m + 1, r, qL, qR);
        }
        return res;
    };

public:
    vector<int> resultArray(vector<int>& nums) {
        // 线段树
        constexpr int maxN = 1e9 + 1;
        Node* root1 = new Node();
        Node* root2 = new Node();

        vector<int> arr1, arr2;
        arr1.push_back(nums[0]);
        update(root1, 1, maxN, nums[0], 1);

        arr2.push_back(nums[1]);
        update(root2, 1, maxN, nums[1], 1);

        for (int i = 2; i < nums.size(); i++) {
            int n1 = query(root1, 1, maxN, nums[i] + 1, maxN);
            int n2 = query(root2, 1, maxN, nums[i] + 1, maxN);
            if (n1 > n2 || (n1 == n2 && arr1.size() <= arr2.size())) {
                update(root1, 1, maxN, nums[i], 1);
                arr1.push_back(nums[i]);
            } else {
                update(root2,1, maxN, nums[i], 1);
                arr2.push_back(nums[i]);
            }
        }
        for (auto& num : arr2) {
            arr1.push_back(num);
        }
        return arr1;
    }
};

//leetcode submit region end(Prohibit modification and deletion)

void print_v(vector<int> arr1) {
    cout << "[";
    for (auto& n : arr1) {
        cout << n << " ";
    }
    cout << "]" << endl;
}

int main() {
    Solution s;
    vector data = {2, 1, 3, 3};
    // print_v(s.resultArray(data));
    data = {5, 14, 3, 1, 2};
    print_v(s.resultArray(data));
}
